package algorithm.stackAndQueue;

import org.omg.PortableInterceptor.INACTIVE;

import javax.print.DocFlavor;
import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public static void main(String[] args) {
//        String ss = removeDuplicates("abbaca");
//        System.out.println(ss);
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(1+1);
        stack.push(1+3);
        stack.push(9);
        System.out.println(stack);// [9, 4, 2]
// 当变量的值与 case 语句的值相等时，那么 case 语句之后的语句开始执行
// ，直到 break 语句出现才会跳出 switch 语句。
//    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>(){
//        @Override
//        public int compare(Integer o1, Integer o2) {
//            return o2-o1;
//        }
//    });
//    maxHeap.offer(33); maxHeap.offer(22);
//    maxHeap.offer(55); maxHeap.offer(11);
//    System.out.println(maxHeap);// [55, 22, 33, 11]
//
//    PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>(){
//        @Override
//        public int compare(Integer o1, Integer o2) {
//            return o1-o2;
//        }
//    });
//    minHeap.offer(33); minHeap.offer(22);
//    minHeap.offer(55); minHeap.offer(11);
//    System.out.println(minHeap);// [11, 22, 55, 33]

//        PriorityQueue<Integer> minHeap = new PriorityQueue<>(Arrays.asList(33,22,55,11));
//        System.out.println(minHeap);// [11, 22, 55, 33]
//
//        PriorityQueue<String> minHeap2 = new PriorityQueue<>(Arrays.asList("33","22","55","11"));
//        System.out.println(minHeap2);// [11, 22, 55, 33]
//
//        PriorityQueue<String> minHeap3 = new PriorityQueue<>(Arrays.asList("cc","bb","dd","22"));
//        System.out.println(minHeap3);// [11, 22, 55, 33]



    }

    PriorityQueue<Integer> A = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            // TODO 自动生成的方法存根
            return o2-o1;
        }
    });

public int[] topKFrequent(int[] nums, int k) {
    // 1、要统计元素出现频率——HashMap<key元素, value次数>
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        map.put(num,map.getOrDefault(num,0)+1);
    }
    //2、对频率排序，找出前K个高频元素——使用优先级队列——小顶堆
    // 小顶堆只需要维护k个有序的序列——每次将队头最小的元素弹出，最后积累的才是前k个最大元素。
    // 队列的元素是：int[] : key 值 + 该值出现的次数。
    //自定义根据次数 排序。 实现这种情况下的小顶堆（实现队头次数最少）
    PriorityQueue<int[]> minHeap = new PriorityQueue<>((o1, o2) ->  o1[1] -o2[1]);

    // map.entrySet() 是 Set<Map.Entry<K, V>> 类型
    for (Map.Entry<Integer, Integer> entry : map.entrySet()){
        //填充 小顶堆，利用 遍历 HashMap 的key、value。
        int[] queueElement = new int[2];
        queueElement[0] = entry.getKey();
        queueElement[1] = entry.getValue();
        minHeap.offer(queueElement);//先插入再判断
        // 只需维护k个, 多了就弹出队头（次数最少）
        if (minHeap.size() >k)
            minHeap.poll();
    }
    //小顶堆填充完了，有K个高频元素。
    int[] res = new int[k];  // 结果：要求返回频率前 k 高的元素
    for (int i = 0; i < k; i++) {
        res[i] = minHeap.poll()[0]; //一进一退
    }
    return res;
}

    public int[] topKFrequent2(int[] nums, int k) {
        // 优先级队列，为了避免复杂 api 操作，pq 存储数组
        // lambda 表达式设置优先级队列从大到小存储 o1 - o2 为从小到大，o2 - o1 反之
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        int[] res = new int[k]; // 答案数组为 k 个元素
        Map<Integer, Integer> map = new HashMap<>(); // 记录元素出现次数
        for(int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        for(Map.Entry<Integer, Integer> x : entries) { // entrySet 获取 k-v Set 集合
            // 将 kv 转化成数组
            int[] tmp = new int[2];
            tmp[0] = x.getKey();
            tmp[1] = x.getValue();
            pq.offer(tmp);
            // 下面的代码是根据小根堆实现的，我只保留优先队列的最后的k个，只要超出了k我就将最小的弹出，剩余的k个就是答案
            if(pq.size() > k) {
                pq.poll();
            }
        }
        for(int i = 0; i < k; i ++) {
            res[i] = pq.poll()[0]; // 获取优先队列里的元素
        }
        return res;
    }











    // 滑动窗口中的最大值
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length-k+1]; //结果集：有len-k +1个。
        // 当前窗口的单调递减队列。
        MyQueue winQueue = new MyQueue();

        int left = 0, right = 0;
        //移动窗口窗口，[left, right) 是左闭右开的，初始时没有包含元素：
        while (right < nums.length){
            winQueue.offerQ(nums[right]); //扩大窗口
            right++;  //  right)

            if (right-left == k){
                //此时窗口正好满了 = k个元素
                res[left] = winQueue.maxQ();// left从0开始，正好可以做为结果数组的下标。
                winQueue.pollQ(nums[left]);//收缩窗口
                left++;
            }
        }
        return res;
    }

    class MyQueue{
        //当前窗口的单调递减队列 。 最大值在队头
        private LinkedList<Integer> queue = new LinkedList<>();

        public void offerQ(int n){
            //如果push的元素n大于队尾的元素，那就将前面小于自己的元素都删除、压没了。直到遇到更大的量级才停住。
            //空-加入。不空并且大于队尾的元素-先压后加入。小于队尾的元素-加入。
            while (!queue.isEmpty() && n > queue.peekLast()){
                queue.pollLast();
            }
            queue.offer(n);
        }

        public void pollQ(int n){
            // 如果窗口移除的元素n，是队头元素，删除队列中的n。
            //如果不是队头元素的话，n比队头小，之前被队头元素压没了，肯定不在队列里面，不用删除。
            if (n == queue.peekFirst())
                queue.pollFirst();

        }
        public int maxQ(){
            return queue.peek();
        }
    }



    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        //使用栈。逆波兰表达式遵循「从左到右」的运算。
       // 所以：从左到右遍历逆波兰表达式，使用 栈 存储操作数:
        int len = tokens.length;

        for (int i = 0; i < len; i++) {
            // 是操作数: 如果遇到操作数，则将操作数入栈；
            if (isOperateNumber(tokens[i])){
                stack.push(Integer.valueOf(tokens[i]));
            }else {
                //如果是运算符，则将两个操作数出栈：：右操作数先出，左操作数后出。
                //运算后，将运算得到的新操作数入栈。
                Integer rightOperate = stack.pop();
                Integer leftOperate = stack.pop();
                switch (tokens[i]){
                    case "+":
                        stack.push(leftOperate + rightOperate);
                        break;
                    case "-":
                        stack.push(leftOperate - rightOperate);
                        break;
                    case "*":
                        stack.push(leftOperate * rightOperate);
                        break;
                    case "/":
                        stack.push(leftOperate / rightOperate);
                        break;
                }
            }
        }
        //整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值。
        return stack.pop();
    }
    // 判断是否是 操作数
    private boolean isOperateNumber(String s){
        if (s.equals("+") || s.equals("-") || s.equals("*") ||s.equals("/")  ){
            return  false;
        }else {
            return true;
        }
    }



    public static String removeDuplicates(String s) {

        //拿字符串直接作为栈 sStack，更方便，不用进行栈还转为字符串了。
        StringBuilder sStack = new StringBuilder();
        // 栈顶
        // 遍历该字符串，
        // 如果当前字符和栈顶字符相同，我们就贪心地将其消去，否则就将其入栈即可。
        for (int i = 0; i < s.length(); i++) {
            //对于 当前字符 s.charAt(i)
            char c = s.charAt(i);
            if(sStack.length()>0 && c == sStack.charAt(sStack.length() -1)){
                sStack.deleteCharAt(sStack.length() -1);
            }else {
                //为空push、 不等的话也push压入栈
                sStack.append(c);
            }
        }
        return sStack.toString();
    }



    public static String removeDuplicates1(String s) {

        Deque<Character> stack = new ArrayDeque<Character>();
        stack.push(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            //我们只需要遍历该字符串，
            // 如果当前字符和栈顶字符相同，我们就贪心地将其消去，否则就将其入栈即可。
            if (!stack.isEmpty() && s.charAt(i) == stack.peek()){
                stack.pop();
            }else {//为空push、 不等的话也push压入栈
                stack.push(s.charAt(i));
            }
        }
        // 从栈中弹出剩余元素 是倒序的，所以再对字符串进行反转一下，
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()){
            sb.append(stack.pop());
        }
        String s1 = sb.reverse().toString();
        return s1;

    }

    private char getLeftMatch(char c){
        if (c == ')' ) {
            return '(';
        } else if (c == '}' ) {
            return '{';
        } else {
            return '[';
        }
    }

    public boolean isValid(String s) {
        //判断成对匹配？
        if (s.length() %2 != 0) return false;
        // 用一个名为 left 的栈代替 left 变量，
        Stack<Character> leftInStack = new Stack<>();

        char[] chars = s.toCharArray();
        for (char c : chars) {
            // 遇到左括号就入栈，
            if ( c == '(' || c == '{' || c == '['){
                leftInStack.push(c);
                // 遇到右括号就去栈中寻找最近的(栈顶的)左括号，看是否匹配：前提是栈不为空。
            }else if (!leftInStack.isEmpty() && getLeftMatch(c) == leftInStack.peek()){
                leftInStack.pop();
            }else {
                //要么为空了（右括号太多），要么不匹配
                return false;
            }
        }
        //全匹配的情况下，栈为空了。（否则"(("的情况。栈就不为空）
        return leftInStack.isEmpty();

    }

}